/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 快速.中间值;

/**
 * @Description 快速排序
 * 是对冒泡排序的一种改进。
 * 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，
 * 其中一部分的所有数据都比另外一部分的所有数据都要小，
 * 然后再按此方法对这两部分数据分别进行快速排序，
 * 整个排序过程可以 递归进行 ，以此达到整个数据变成有序序列
 * 以中间为基准
 * @Author 俊昭
 * @Date 2022/5/1
 */
public class Quick {
    //基于韩老师的版本 比较复杂 需要考虑更多情况 推荐边值基准版本
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }


    private static void sort(int[] arr, int left, int right) {
        // 初始化时左右指针分别为第一和最后一个下标
        int l = left;
        int r = right;
        int value = arr[(l + r) / 2];
        // 只要左指针在右指针左边
        while (l < r) {
            // 记录下两边不符合排序规则的数的位置
            // 或到两指针相遇
            while (arr[l] < value) {
                l++;
            }
            while (arr[r] > value) {
                r--;
            }
            if (l >= r) {
                break;
            }
            // 交换两指针对应值
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            // 调整指针位置
            if (arr[r] == value) {
                l++;
            }
            if (arr[l] == value) {
                r--;
            }
        }
        // 避免死循环
        if (l == r) {
            r--;
            l++;
        }
        // 将r ,l 作为下次排序的初始条件
        if (r > left) {
            sort(arr, left, r);
        }
        if (l < right) {
            sort(arr, l, right);
        }
    }
}
/*
    public static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    //优化Code阅读版本 还是较为复杂 推荐边值基准版本
    private static void sort(int[] arr, int start, int end) {
        if (start < end) {
            int mid =(start+end)>>1;
            int base = arr[mid];
            int low = start;
            int high = end;

            while (true) {
                while (low < end && arr[low] <= base) {
                    low++;
                }
                while (high > start && arr[high] >= base) {
                    high--;
                }
                if (low < high) {
                    swap(arr, low, high);
                } else {
                    break;
                }
            }
            swap(arr, mid, high);// 将base的值给到两指针相遇的的地方 左全小于基准 同理右全大于基准

            //递归处理
            sort(arr, start, high - 1);// 左边
            sort(arr, low + 1, end);// 右边
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
*/

